#!/usr/bin/env python

#Very much a draft.
import itertools, sys

#ercset1s = sys.argv[-2]
#ercset2s = sys.argv[-1]

#ercset1 = ercset1s.rsplit("_")
#ercset2 = ercset2s.rsplit("_")
#print ercset1
#print ercset2

def compatible(r, erc):
	"""Check if two ERCs are compatible"""
	havew = False
	for i in range(len(r)):
		if erc[r[i]] == 'w':
			havew = True
		elif erc[r[i]] == 'l' and not havew:
			return False
	return True

def getrankings(ercset, n=0):
	"""Get all of the rankings consistent with an erc set"""
	pset = itertools.permutations(range(len(ercset[0])))
	psetl = list(pset)
	ret = []
	for p in psetl:
		okay = True
		for erc in ercset:
			if okay and not compatible(p, erc):
				okay = False
		if okay:
			ret.append(p)
		if n!=0 and len(ret)>n-1:
			return ret
	
	return ret
	
#Below: Code for permutation distance testing
def merge_and_count(a, b):
    assert a == sorted(a) and b == sorted(b)
    c = []
    count = 0
    i, j = 0, 0
    while i < len(a) and j < len(b):
        c.append(min(b[j], a[i]))
        if b[j] < a[i]:
            count += len(a) - i # number of elements remaining in `a`
            j+=1
        else:
            i+=1
    # now we reached the end of one the lists
    c += a[i:] + b[j:] # append the remainder of the list to C
    return count, c


def sort_and_count(L):
    if len(L) == 1: return 0, L
    n = len(L) // 2 
    a, b = L[:n], L[n:]
    ra, a = sort_and_count(a)
    rb, b = sort_and_count(b)
    r, L = merge_and_count(a, b)
    return ra+rb+r, L


def get_permutation(L1, L2):
    """Find permutation that converts L1 into L2.

    See http://en.wikipedia.org/wiki/Cycle_representation#Notation
    """
    if sorted(L1) != sorted(L2):
        raise ValueError("L2 must be permutation of L1 (%s, %s)" % (L1,L2))

    permutation = map(dict((v, i) for i, v in enumerate(L1)).get, L2)
    assert [L1[p] for p in permutation] == L2
    return permutation


def number_of_swaps(permutation):
	"""Find number of swaps required to convert the permutation into
	identity one.
	
	 """
	# decompose the permutation into disjoint cycles
	nswaps = 0
	seen = set()
	for i in xrange(len(permutation)):
		if i not in seen:   
			j = i
			while permutation[j] != i:
				j = permutation[j]
				seen.add(j)
				nswaps += 1

	return nswaps

def set_dif(rset1, rset2):
	"""Get the minimum distance between rankings defined by two erc sets, and the best rankings"""
	m = -1
	pairs = []
	i = 0
	for r1 in  rset1:
		if i%50==0:
			print  "Processing ranking", i+1,'/',len(rset1),"..."
		i+=1
		for r2 in rset2:
			per = get_permutation(list(r1),list(r2))
			dist = sort_and_count(per)[0]
			if m > 0 and dist < m:
				m = dist
				pairs = []
				pairs.append([r1, r2])
			elif m < 0:
				m = dist
				pairs.append([r1, r2])
			elif dist == m:
				pairs.append([r1, r2])
	return [m, pairs]
	

#Get permutation sets, compute distances, find min

#r1 = getrankings(ercset1)
#r2 = getrankings(ercset2)

#print r1
#print r2

#print set_dif(r1, r2)
